package com.zhanghp.class07;

/**
 * <h1>左神基于我的错误快排讲解！这个是正确的！</h1>
 *
 * @author zhanghp
 * @since 2024/2/3 17:56
 */
public class Code04_PartitionAndQuickSort_Zuo_Answer {

    // 测试链接 : https://leetcode.cn/problems/sort-an-array/
    public static int[] sortArray(int[] nums) {
        quickSort(nums);
        return nums;
    }

    public static void quickSort(int[] arr) {
        process(arr, 0, arr.length - 1);
    }

    public static void process(int[] arr, int L, int R) {
        // 这里你写错了！
        if (L >= R) {
            return;
        }
        // 为什么不用随机？！
        // 轩墨：这涉及到对时间复杂度的一个优化，避免选择到最差的一个情况 导致时间复杂度很高
        swap(arr, L + (int) (Math.random() * (R - L + 1)), R);
        int[] partition = partition(arr, L, R);
        // 这里你写错了！自己看你写的啥
        process(arr, L, partition[0]);
        process(arr, partition[1], R);
    }

    // 你这代码错误也太多了
    public static int[] partition(int[] arr, int L, int R) {
        int lIndex = L - 1; // 改这里
        int rIndex = R;
        int pointer = L;
        int fixVal = arr[R];
        while (pointer != rIndex) { // 改这里
            int curVal = arr[pointer];
            if (curVal < fixVal) {
                swap(arr, ++lIndex, pointer++); // 改这里
            } else if (curVal == fixVal) {
                pointer++;
            } else {
                swap(arr, --rIndex, pointer);// 改这里
            }
        }
        swap(arr, pointer, R); // 改这里
        return new int[] { lIndex, pointer }; // 改这里
    }

    public static void swap(int[] arr, int a, int b) {
        int temp = arr[a];
        arr[a] = arr[b];
        arr[b] = temp;
    }



}
